A fixed point (or fixpoint) of an endofunction is an element such that .
More generally, if is a category with a terminal object and an endomorphism , then a fixed point of is an element such that . More generally still, we can speak of the same notion but replacing global elements by generalized elements , where again is a fixed point of if .
Fixed points are also called invariants, in particular if they are joint fixed points of all the operations in a given monoid or group.
Such fixed points we discuss below in
The importance of fixed points all throughout mathematics is difficult to overstate. They are particularly important in analysis, topology, lattice theory, set theory, and category theory. Fixed points of endofunctors frequently arise as solutions to “recursive equations”, especially in the form of initial algebras and terminal coalgebras.
In category theory the concept of fixed points admits categorification: For example, if is an endofunctor, then an object of is called a “fixed point of the endofunctor” is there is an isomorphism (although usually, a fixed point of a functor is an object together with a specified such isomorphism). These fixed points for endofunctors we discuss below in
See also at
In homotopy theory the concept of fixed point becomes that of
In stable homotopy theory it becomes the concept of
For further occurences in logic see also
A typical application of fixed points in analysis is through the following general theorem:
Suppose is an (inhabited) complete metric space with distance function and is a function with Lipschitz constant less than , i.e., for all . Then has a unique fixed point.
The proof is very easy: starting with an initial point , the sequence defined by is readily seen to be a Cauchy sequence which converges to some point . The sequence converges to both and , so . If and are fixed points, then , so
whence and therefore .
By a suitable choice of space and endomorphism , this theorem can be used to establish existence and uniqueness of solutions of differential equations (this should be expanded upon).
In the case where is compact, we may weaken the condition for some uniform , to merely whenever . To see this, use compactness to show that attains a minimum value at some . Then , else . Hence there exists at least one fixed point, and only one since if are different fixed points, then .
Schauder
Kakutani
Tychonoff
Lefschetz
Atiyah-Singer; Wood’s Hole
If is a complete lattice, then every monotone (i.e., order-preserving) map has a fixed point (in fact, the fixed points of form a complete lattice).
The algebras for the functor are elements such that . Limits in are preserved and reflected by the forgetful functor or inclusion , hence is complete if is. In particular, has an initial object, and initial algebras are fixed points.
(In more down-to-earth terms, let be the infimum of . Then for every , we have , hence . We therefore also have , so that . But then it follows that , whence . Clearly this is a least fixed point of .)
To show completeness of , suppose given , and let be the supremum of in . Then the principal upward-closed set generated by is a complete lattice. Also, restricts to a map (for if , then for all , whence for all , so that ). The least fixed point of is the supremum of in .
A virtual corollary of this theorem is the Cantor-Schroeder-Bernstein theorem.
The following significantly strengthens the Knaster-Tarski theorem, and is based on the notion of an ipo (inductive partial order; see Paul Taylor’s book), i.e., a poset with a bottom element and admitting joins of directed subsets.
(Pataraia)
If is an ipo, then every monotone map has a (least) fixed point.
Consider the smallest among subsets of which contain , are closed under , and closed under directed joins in . Then the restriction satisfies , i.e., is inflationary. (For the set of all elements such that is another such subset, so is contained in it.) Thus it suffices to show that every inflationary map on a poset with a bottom element and directed joins has a fixed point.
The collection of inflationary monotone maps on is an ipo: its bottom element is , and directed joins are computed pointwise. Moreover, is itself directed: if , then dominates them both. Thus the directed join of the collection exists; it is the maximal element of . It follows that , but also since is inflationary. So , and in particular is a fixed point of .
This is a least fixed point of . For if is any fixed point, the downward-closed set contains , is closed under , and is closed under directed unions, and therefore . Hence satisfies .
One may mimic the last part of the proof of the Knaster-Tarski theorem to show that if is an ipo and is monotone, then (with the order inherited from ) is also an ipo. Indeed, we have just seen has a bottom element, and if is any directed subset, and is its sup in , then we may argue as we did for the Knaster-Tarski theorem that restricts to a monotone map on the ipo , whence by Pataraia’s theorem it has a least fixed point, and this will be the sup of in .
The identity function on a set is the unique function on such that every element in is a fixed point of said function.
In at least some of the “lower” levels of the hierarchy of countable ordinals, leading up to the Feferman-Schütte ordinal, fixed points of continuous operators on the first uncountable ordinal play a central role. More information may be found at countable ordinal.
Critical points of elementary embeddings (non-fixed points)
Various classical fixed-point theorems for monotone functions on posets can be “categorified” to give appropriate fixed-point theorems for endofunctors on categories. An example is that Kleene's fixed-point theorem generalizes to Adámek's fixed point theorem:
Let be a category with an initial object and colimits of -directed diagrams for some regular cardinal , and suppose preserves -directed colimits. Then has an initial algebra (which by Lambek's theorem is a fixed point of ).
Regarding as an ordinal (hence a poset, hence a category), define a functor recursively: on objects, put , , and for a limit ordinal. On morphisms ,
is the unique map ;
For a limit ordinal, is a component of the cocone diagram that defines as a colimit;
;
For a limit ordinal, is the unique map corresponding to the cocone from the diagram to .
By assumption, exists in , and this colimit is preserved by . Thus we have an isomorphism , affording an -algebra structure on . If is any algebra, then we define a cocone from to whose component at successor stages is defined recursively as an evident composite
and whose component at limit stages is the unique map out of the colimit that is compatible with previous components , for . It is readily seen that the map , uniquely determined from the cocone , is the only possible algebra map.
A typical application is where is a -accessible category and is a -accessible functor. A concise statement is that accessible endofunctors on accessible categories with an initial object possess categorical fixed points (in fact, the fixed points form another accessible category with an initial object).
An arguably more elegant viewpoint on this is given in the following theorem and proof.
Suppose is locally presentable, i.e., accessible and complete/cocomplete, and suppose is an accessible functor. Then the category of -algebras is also locally presentable. In particular, there exists an initial -algebra. Moreover, the category of fixed points, i.e., the category of -algebras for which the structure is an isomorphism is also locally presentable (in particular, cocomplete and complete).
is an inserter construction, i.e., the data consisting of the evident 1-cell and 2-cell is universal among all such data in the 2-category . Since is closed under 2-limits in such as inserters (see Makkai-Paré, theorem 5.1.6), the category is accessible. It is also complete since is complete (being locally presentable) and the underlying functor reflects limits. Since is accessible and complete, it is also cocomplete, hence contains an initial object.
Similarly, the category of fixed points is formed as an iso-inserter construction and is therefore accessible. If is a diagram of fixed points and is the colimit of , then induces a functor (which we give the same name) , because for any object in , we have a cocone , factoring uniquely through an arrow . Since is a locally presentable category, the accessible functor acting on it has an initial algebra , as we argued before. This is the colimit of in , as is easily checked. Therefore is cocomplete and accessible.
Boundedness conditions, such as those given as hypotheses in the previous two theorems, are generally required to establish existence of categorical fixed points. The example of the covariant power-set functor on shows that a naive generalization of the Knaster-Tarski theorem from complete lattices to complete/cocomplete categories is hopelessly false.
Paul Taylor has built an elegant theory of locating certain initial algebras inside final coalgebras, via his notion of well-founded coalgebras. This too can be “categorified” (to be continued).
Let be a topos, and let be a left-exact idempotent functor. Then the category of -coalgebras whose structure maps are isomorphisms is a topos.
Here “idempotent” involves a coassociativity condition.
This theorem is a special case of a general theorem about categories of dialgebras for a diad?.
Todd: To be related to structures over a modal operator, as at my web, or to diads a la Toby Kenney.
including fixed points of Galois correspondences
Theorems
Claudio Hermida, Bart Jacobs, Structural induction and coinduction in a fibrational setting, Information and Computation 145 (1997), 107-152. (citeseer)
Michael Makkai, Robert Paré, Accessible Categories: The Foundations of Categorical Model Theory, Contemporary Mathematics 104, AMS (1989).
Wikipedia, Fixed point (mathematics)
A version of the Knaster-Tarski fixed-point theorem is proved in constructive (and even predicative) set theory in
as well as in dependent type theory in
A relation to framed cobordism classes and fixed points:
Carlos Prieto, Fixed point theory and framed cobordism, Topol. Methods Nonlinear Anal. Volume 21, Number 1 (2003), 155-169. (Euclid)
Robert Paré, R. Rosebrugh and R. J. Wood, Idempotents in bicategories, Bulletin of the Australian Mathematical Society, Vol. 39, No. 3, 1989, pp. 421-434. [doi:10.1017/S0004972700003336]
Toby Kenney, Diads and their Application to Topoi, Applied Categorical Structures 17 (2009): 567-590.
Last revised on September 22, 2024 at 06:07:43. See the history of this page for a list of all contributions to it.